home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 008a / revpolno.zip / RPN.TXT
Text File  |  1991-12-01  |  12KB  |  236 lines
  1.                       UNDERSTANDING REVERSE-POLISH NOTATION
  2.         
  3.         For those of us using or considering a Hewlett-Packard scientific 
  4.         calculator or computer, the question often arises, "What the heck 
  5.         is Reverse-Polish Notation?"
  6.         
  7.         The conventional mathematical notation we learned in high school 
  8.         is known as "Algebraic Notation."  In this notation, the 
  9.         operators are placed either between or in front of the arguments.  
  10.         Operators designate the operation to be performed ("+", "*", 
  11.         "sin", etc.) and arguments are the values or variables upon which 
  12.         they act ("1", "42.5", "pi", "x", etc.).  A typical mathematical 
  13.         expression might be:
  14.         
  15.           sin[123 + 45 ln(27 - 6)]
  16.         
  17.         The operators in this expression, from left to right, are "sin", 
  18.         "+", "*" (implied between "45" and "ln"), "ln", and "-".  By 
  19.         their natures, "sin" and "ln" require one argument each while 
  20.         "+", "*", and "-" require two each.
  21.         
  22.         The arguments are not so easily determined.  At first glance they 
  23.         appear to be "123", "45", "27", and "6", but this is patently 
  24.         false!  The argument of "sin" is everything within the brackets, 
  25.         or "123 + 45 ln(27 - 6)", those of "+" are "123" and "45 ln(27 - 
  26.         6)", those of "*" are "45" and "ln(27 - 6)", that of "ln" is "27 
  27.         - 6", and those of "-" are "27" and "6".
  28.         
  29.         The whole expression may be thought of as a series of separate 
  30.         operations:
  31.         
  32.           sin[123 + 45 ln(27 - 6)] = sin(a) :: a = 123 + 45 ln(27 - 6)
  33.           123 + 45 ln(27 - 6) = 123 + b     :: b = 45 ln(27 - 6)
  34.           45 ln(27 - 6) = 45 * c            :: c = ln(27 - 6)
  35.           ln(27 - 6) = ln(d)                :: d = 27 - 6
  36.           27 - 6
  37.         
  38.         It is because of this that complex expressions are performed from 
  39.         the inside out:
  40.         
  41.           sin[123 + 45 ln(27 - 6)]      = sin[123 + 45 ln(21)
  42.           sin[123 + 45 ln(21)]          = sin(123 + 45 * 3.04452243772)
  43.           sin(123 + 45 * 3.04452243772) = sin(123 + 137.003509697)
  44.           sin(123 + 137.003509697)      = sin(260.003509697)
  45.           sin(260.003539697)            = 0.680672740775
  46.         
  47.         In this manner, it can easily be seen that each operation is a 
  48.         function of its argument or arguments, and an argument may itself 
  49.         be a function of other arguments.  Therefore, if we were to treat 
  50.         the operations exactly as functions of arguments in the 
  51.         traditional ƒ(x) and ƒ(y,x) formats, the expression "27 - 6" 
  52.         would become -(27,6), where "-" is the operator "ƒ", "27" is the 
  53.         argument "y", and "6" is the argument "x":
  54.  
  55.           27 - 6  ──>  -(27,6)
  56.         
  57.         This is a two-argument function:  in any two-argument function, 
  58.         the second argument will always act against the first argument.  
  59.         In this case, the second argument "6" will be subtracted from the 
  60.         first argument "27".
  61.         
  62.         The concept of treating all operators as functions is not as 
  63.         strange as it first appears when you consider that a considerable 
  64.         number of operators are already functions:  ln(x) is ƒ(x) where 
  65.         "ƒ" is "ln".
  66.         
  67.         In the case of our example expression, the next function out is 
  68.         ln(d), where "d" is itself the function -(27,6):
  69.         
  70.           27 - 6                   ──> -(27,6)
  71.           ln(27 - 6)               ──> ln(-(27,6))
  72.           45 ln(27 - 6)            ──> *(45,ln(-(27,6)))
  73.           123 + 45 ln(27 - 6)      ──> +(123,*(45,ln(-(27,6))))
  74.           sin[123 + 45 ln(27 - 6)] ──> sin(+(123,*(45,ln(-(27,6)))))
  75.         
  76.         The final function sin(+(123,*(45,ln(-(27,6))))) may at first 
  77.         seem confusing, especially with all the parentheses, until one 
  78.         remembers that it is the one-argument function sin(x).  Once this 
  79.         is realized, then everything within the parenthesis following 
  80.         "sin" must be the one and only argument of sin():  the argument 
  81.         of sin() must be +(123,*(45,ln(-(27,6)))).
  82.         
  83.         In a similar manner, +(123,*(45,ln(-(27,6)))) is the two-argument 
  84.         function +(y,x), where "y" is "123" and "x" is *(45,ln(-(27,6))).
  85.         
  86.         A further clarification can be made if "+(y,x)" is thought of as 
  87.         "the sum of y and x" (just as "ln(x)" is "the natural logarithm 
  88.         of x").  This approach allows "sin(+(123,*(45,ln(-(27,6)))))" to 
  89.         be read as "the sine of the sum of 123 and the product of 45 and 
  90.         the natural logarithm of the difference of 27 and 6."  This 
  91.         phrase readily illustrates its clarity when empasized function by 
  92.         function:
  93.         
  94.           sin(+(123,*(45,ln(-(27,6)))))
  95.         
  96.           The sine of                       sin(...)
  97.           the sum of                        sin(+(...))
  98.           123 and the product of            sin(+(123,*(...)))
  99.           45 and the natural logarithm of   sin(+(123,*(45,ln(...))))
  100.           the difference of                 sin(+(123,*(45,ln(-(...)))))
  101.           27 and 6.                         sin(+(123,*(45,ln(-(27,6)))))
  102.         
  103.         Awkward as that may seem, it is much cleaner and more 
  104.         straightforward than "sin[123+45ln(27-6)]," which is "the sine of 
  105.         the quantity 123 plus 45 times the natural logarithm of the 
  106.         quantity 27 minus 6."
  107.         
  108.         What is even more important, it is unambiguous!  If you heard 
  109.         someone say "the quantity 123 plus 45 times the natural logarithm 
  110.         of ...," does the speaker mean "(123+45)ln()" or 
  111.         "(123+(45ln()))".  By defining all operations as functions there 
  112.         is no ambiguity, ever!
  113.         
  114.         In algebra, a complex set of rules has been established as 
  115.         regards order and priority of operations, and if these rules are 
  116.         strictly followed there will be no ambiguity.  Unfortunately, few 
  117.         of the "algebraic" calculators or software packages on the market 
  118.         follow these rules properly, and there is a total lack of 
  119.         consistency in which rules are overlooked or changed.
  120.         
  121.         What is needed with a calculator or computer is a mechanistic and 
  122.         totally unambiguous method of operation.  Treating all arguments 
  123.         as functions provides just such a method and is known as Polish 
  124.         Notation after its creator, the Polish logician Jan Lukasiewicz.  
  125.         The complex function sin(+(123,*(45,ln(-(27,6))))) has one and 
  126.         only one possible meaning, whether written in mathematical 
  127.         symbology or spoken aloud.
  128.         
  129.         Further research by the logicians at Hewlett-Packard provided a 
  130.         slight variation on the theme.  If instead of placing the 
  131.         function ahead of its argument(s), it is placed behind, we get:
  132.         
  133.           sin(+(123,*(45,ln(-(27,6)))))
  134.           ─────────────────────────────
  135.           sin(                        ) ──> (                        )sin
  136.               +(123,                 )  ──>  (123,                 )+
  137.                     *(45,           )   ──>       (45,           )*
  138.                          ln(       )    ──>           (       )ln
  139.                             -(27,6)     ──>            (27,6)-
  140.                                             ─────────────────────────────
  141.                                             ((123,(45,((27,6)-)ln)*)+)sin
  142.         
  143.         This method is known as Reverse Polish Notation, or RPN, in honor 
  144.         of the original method.  RPN, like Polish Notation, is 
  145.         unambiguous:  the order and only the order of arguments and 
  146.         operators will determine the result.  Since this is the case, the 
  147.         parentheses and commas are irrelevant, and we may express our 
  148.         function as:
  149.         
  150.           ((123,(45,((27,6)-)ln)*)+)sin  ──>  123 45 27 6 - ln * + sin
  151.         
  152.         This allows a simple and straightforward solution to calculator 
  153.         or software mathematics:  treat both the functions and their 
  154.         arguments alike as "objects," and process them in a last-in, 
  155.         first-out (LIFO) storage structure, a "stack."
  156.         
  157.         When a function-object is entered onto the stack, it operates 
  158.         upon the argument-object(s) already there to produce a result, 
  159.         which replaces the argument-object(s).  The stack adjusts 
  160.         accordingly.  This can be seen as:
  161.  
  162.           object    stack level x:                  y:    z:    t:
  163.           ──────  ┌───────────────────────────────┬─────┬─────┬─────┐
  164.           123     │ 123                           │     │     │     │
  165.           45      │ 45                            │ 123 │     │     │
  166.           27      │ 27                            │ 45  │ 123 │     │
  167.           6       │ 6                             │ 27  │ 45  │ 123 │
  168.           -       │ -(27,6)                       │ 45  │ 123 │     │
  169.           ln      │ ln(-(27,6))                   │ 45  │ 123 │     │
  170.           *       │ *(45,ln(-(27,6)))             │ 123 │     │     │
  171.           +       │ +(123,*(45,ln(-(27,6))))      │     │     │     │
  172.           sin     │ sin(+(123,*(45,ln(-(27,6))))) │     │     │     │
  173.                   └───────────────────────────────┴─────┴─────┴─────┘
  174.         
  175.         The secret behind RPN's sophisticated yet simple power is in the 
  176.         stack.  In computer terms, a stack is an area in which pieces of 
  177.         information may be stored on a last-in, first-out (LIFO) basis.  
  178.         Think of the stack as a stack of plates:  the last plate placed 
  179.         on the stack will be the first plate used.
  180.         
  181.         Most simple RPN calculators use a four-level stack, with the 
  182.         levels labeled "x", "y", "z", and "t".  Some newer, more 
  183.         sophisticated calculators (such as the HP-28S and the HP-48SX) 
  184.         and most software programs use an "infinite" stack:  the number 
  185.         of stack levels is limited only by available memory.  The levels 
  186.         in an infinite stack are usually numerical.
  187.         
  188.         Entering a value will cause a stack lift:  existing values will 
  189.         be pushed up a level.
  190.         
  191.         Entering a function will consume the arguments of the function.  
  192.         If this consumption causes a "hole," the values above the hole 
  193.         will be dropped to fill the hole.
  194.         
  195.         Following through our example on an HP-48SX calculator:
  196.         
  197.                   ┌───────────────────┐
  198.              123  │ 1:            123 │
  199.                   └───────────────────┘
  200.                   ┌───────────────────┐
  201.                   │ 2:            123 │
  202.              45   │ 1:             45 │
  203.                   └───────────────────┘
  204.                   ┌───────────────────┐
  205.                   │ 3:            123 │
  206.                   │ 2:             45 │
  207.              27   │ 1:             27 │
  208.                   └───────────────────┘
  209.                   ┌───────────────────┐
  210.                   │ 4:            123 │
  211.                   │ 3:             45 │
  212.                   │ 2:             27 │
  213.              6    │ 1:              6 │
  214.                   └───────────────────┘
  215.                   ┌───────────────────┐
  216.                   │ 3:            123 │
  217.                   │ 2:             45 │
  218.              -    │ 1:             21 │ -(27,6)
  219.                   └───────────────────┘
  220.                   ┌───────────────────┐
  221.                   │ 3:            123 │
  222.                   │ 2:             45 │
  223.              ln   │ 1:  3.04452243772 │ ln(-(27,6))
  224.                   └───────────────────┘
  225.                   ┌───────────────────┐
  226.                   │ 2:            123 │
  227.              *    │ 1:  137.003509697 │ *(45,ln(-(27,6)))
  228.                   └───────────────────┘
  229.                   ┌───────────────────┐
  230.              +    │ 1:  260.003509697 │ +(123,*(45,ln(-(27,6))))
  231.                   └───────────────────┘
  232.                   ┌───────────────────┐
  233.              sin  │ 1:  .680672740775 │ sin(+(123,*(45,ln(-(27,6)))))
  234.                   └───────────────────┘
  235.  
  236.